package me.chenqiang.cinc.passportutils;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;

public class StringPrefixFreeCodecTrie<T> {
	public static class Node<T> {
		protected Map<Character, Node<T>> children;
		protected T value;
		public Node(T value) {
			super();
			this.children = new HashMap<>();
			this.value = value;
		}
		public Map<Character, Node<T>> getChildren() {
			return children;
		}
		public T getValue() {
			return value;
		}	
	}
	
	protected Node<T> root;

	public StringPrefixFreeCodecTrie() {
		this.root = new Node<>(null);		
	}
	
	@SuppressWarnings("unchecked")
	protected T convert(String key) {
		return (T)key;
	}
	
	public void insert(String key, T value) {
		Node<T> node = this.root;
		for(int i = 0; i < key.length(); i++) {
			char letter = key.charAt(i);
			if(!node.children.containsKey(letter)) {
				node.children.put(letter, new Node<>(null));
			}
			node = node.children.get(letter);
			if(node.value != null) {
				throw new IllegalArgumentException(String.format("当前单词的前缀%s已经存在，不符合PFC规则", key.substring(0, i + 1)));
			}
		}
		if(!node.children.isEmpty()) {
			throw new IllegalArgumentException(String.format("存在以当前单词%s为前缀的其他单词，不符合PFC规则", key));
		}
		node.value = value == null ? convert(key) : value;
	}
	
	public T getValue(String key) {
		Node<T> node = this.root;
		for(int i = 0; i < key.length(); i++) {
			char letter = key.charAt(i);
			if(!node.children.containsKey(letter)) {
				return null;
			}
		}
		return node.value;
	}
	
	protected class DecodeIterator implements Iterator<Entry<String, T>> {
		protected int start;
		protected int cursor;
		protected CharSequence sequence;
		protected Node<T> node;
		
		public DecodeIterator(CharSequence sequence) {
			this.sequence = sequence;
			this.cursor = 0;
			this.start = 0;
			this.node = StringPrefixFreeCodecTrie.this.root;
		}

		@Override
		public boolean hasNext() {
			return this.start < this.sequence.length();
		}

		@Override
		public Entry<String, T> next() {
			if(!hasNext()) {
				throw new NoSuchElementException();
			}
			while(this.node.value == null) {
				char letter = this.sequence.charAt(this.cursor);
				if(!this.node.children.containsKey(letter)) {
					throw new IllegalArgumentException(
							String.format("单词前缀%s不属于合法编码", this.sequence.subSequence(this.start, this.cursor)));
				}
				this.node = this.node.children.get(letter);
				this.cursor ++;
				if(this.cursor > this.sequence.length()) {
					throw new IllegalArgumentException(
							String.format("编码不完整：剩余%s不属于合法编码", this.sequence.subSequence(this.start, this.cursor)));
				}
			}
			Entry<String, T> res = Map.entry(this.sequence.subSequence(this.start, this.cursor).toString(), this.node.value);
			this.start = this.cursor;
			this.node = StringPrefixFreeCodecTrie.this.root;
			return res;			
		}
		
	}
	
	public Iterator<Entry<String, T>> iterator(CharSequence sequence) {
		return new DecodeIterator(sequence);
	}
	
	public Iterable<Entry<String, T>> items(CharSequence sequence) {
		return () -> StringPrefixFreeCodecTrie.this.iterator(sequence);	}
	
	
	public static <T> StringPrefixFreeCodecTrie<T> build(Iterable<Entry<String, T>> entries) {
		StringPrefixFreeCodecTrie<T> tree = new StringPrefixFreeCodecTrie<>();
		for(Entry<String, T> entry: entries) {
			tree.insert(entry.getKey(), entry.getValue());
		}
		return tree;
	}
	
}
